package com.sali.Tree;

/**
 * 给定一个单链表的头节点  head ，其中的元素 按升序排序 ，将其转换为 平衡 二叉搜索树。
 */
public class LeetCode_109 {

    public TreeNode sortedListToBST(ListNode head) {
        return mySolve(head, null);
    }

    private TreeNode mySolve(ListNode left, ListNode right) {
        if (left == right) return null;

        ListNode slowNode = left;
        ListNode fastNode = left;

        while (fastNode != right && fastNode.next != right) {
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
        }

        TreeNode cur = new TreeNode(slowNode.val);
        cur.left = mySolve(left, slowNode);
        cur.right = mySolve(slowNode.next, right);
        return cur;
    }

}


class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}